package com.likou.second_challenge;

import java.util.*;

public class q42 {

    // 栈
    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && height[i] > height[deque.peek()]) {
                Integer poll = deque.poll();
                if (deque.isEmpty()) {
                    break;
                }
                Integer peek = deque.peek();
                int kuang = i - peek - 1;
                int h = Math.min(height[i], height[peek]) - height[poll];
                ans += kuang * h;
            }
            deque.push(i);
        }

        return ans;
    }


    // 双指针
//    public int trap(int[] height) {
//        int n = height.length;
//
//        int leftMax = 0;
//        int rightMax = 0;
//        int left = 0;
//        int right = n - 1;
//        int ans = 0;
//        while (left < right) {
//            if (height[left] < height[right]) {
//                leftMax = Math.max(leftMax, height[left]);
//                ans += leftMax - height[left];
//                left++;
//            } else {
//                rightMax = Math.max(rightMax, height[right]);
//                ans += rightMax - height[right];
//                right--;
//            }
//        }
//        return ans;
//    }

    // 前缀和
//    public int trap(int[] height) {
//        int n = height.length;
//
//        int[] leftMax = new int[n];
//        leftMax[0] = height[0];
//        for (int i = 1; i < n; i++) {
//            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
//        }
//
//        int[] rightMax = new int[n];
//        rightMax[n - 1] = height[n - 1];
//        for (int i = n - 2; i >= 0; i--) {
//            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
//        }
//
//        int ans = 0;
//        for (int i = 1; i < n - 1; i++) {
//            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
//        }
//
//        return ans;
//    }
}
